public class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int total = len1 + len2;
        if ((total & 1) == 1) {
            return getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, (total + 1) / 2);
        } else {
            return (getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, total / 2) +
                    getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, total / 2 + 1)) / 2.0;
        }
    }

    private int getKth(int[] nums1, int s1, int t1, int[] nums2, int s2, int t2, int k) {
        int len1 = t1 - s1 + 1;
        int len2 = t2 - s2 + 1;
        if (len1 == 0)
            return nums2[s2 + k - 1];
        if (len2 == 0)
            return nums1[s1 + k - 1];
        if (k == 1)
            return Math.min(nums1[s1], nums2[s2]);

        int i = s1 + Math.min(len1, k / 2) - 1;
        int j = s2 + Math.min(len2, k / 2) - 1;
        if (nums1[i] <= nums2[j]) {
            return getKth(nums1, i + 1, t1, nums2, s2, t2, k - Math.min(len1, k / 2));
        } else {
            return getKth(nums1, s1, t1, nums2, j + 1, t2, k - Math.min(len2, k / 2));
        }
    }
}
